#include <stdio.h>
#include <stdlib.h>

#define null 0

/**
 * 队列Queue是具有一定操作约束的线性表
 * 只能在一段插入，在另一端删除（先进后出）
 * 基于链表实现的队列
 */ 

//队列的结点
struct Node{
    int Data;
    struct Node *Next;
};

//链结构队列
struct QNode{
    struct Node *rear;//指向队尾结点
    struct Node *front;//指向队头结点
};

typedef struct Node *QNodePtr;
typedef struct QNode *Queue;
Queue PtrQ;

int deleteQ(Queue PtrQ);
void addQ(Queue PtrQ, int elem);
void show(Queue PtrQ);
Queue Q_Init();

int main(){
    printf("main start..\n");
    // Queue q = (Queue)malloc(sizeof(struct QNode));
    Queue q = Q_Init();
    addQ(q,1);
    addQ(q,2);
    deleteQ(q);
    show(q);
    printf("over\n");
    return 0;
}

void addQ(Queue PtrQ, int elem){
    QNodePtr p = (QNodePtr)malloc(sizeof(struct Node));
    if(!p){
        printf("分配失败");
        exit(-1);
    }
    p->Data = elem;
    p->Next = NULL;
    //关键点：新增节点在队尾插入，
    PtrQ->rear->Next = p;
    PtrQ->rear = p;
}

int deleteQ(Queue PtrQ){
    struct Node *FrontCell;
    int FrontElem;

    if(PtrQ->front == NULL){
        printf("队列为空");
        return null;
    }
    FrontCell = PtrQ->front;
    if(PtrQ->front == PtrQ->rear){
        PtrQ->front = PtrQ->rear = NULL;
    }else{
        PtrQ->front = PtrQ->front->Next;
    }
    FrontElem = FrontCell->Data;
    free(FrontCell);
    return FrontElem;
}

void show(Queue q){
    printf("start show: ");
    int i =0;
    QNodePtr p;
    p = q->front;
    while(q->rear != p){
        i++;
        printf(" %d ", p->Next->Data);
        p = p->Next;
    };
    printf("\n");
}

//构造一个空队列Q
Queue Q_Init() {
    //申请内存
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    //如果 Q 为 NULL 说明 内存申请失败，结束程序
    if (!Q)
        exit(-1);
    //关键点：初始化头尾节点 指向相同地址
    Q->front = Q->rear = (QNodePtr)malloc(sizeof(struct Node));
    //如果 Q->front 为 NULL 说明 内存申请失败，结束程序
    if (!Q->front)
        exit(-1);
    Q->front->Next = NULL;
    return Q;

}
